The present invention relates to a cache flush unit and method for use in a computer system constituted by a uniprocessor or a multiprocessor having a cache.
In a general computer, a cache for temporarily storing data required by the processor is used to increase the speed of access from the processor to the main memory. Normally, the cache holds data as data units with a predetermined size, which are called cache blocks. The cache also holds management information called a cache tag to manage the correspondence between cache block data stored in the cache and data in the main memory, and whether the data is changed by the processor, i.e., different from contents in the main memory (modified state or dirty state).
A computer system having a plurality of processors (multiprocessor system) often uses caches each having a snoop mechanism to guarantee data consistency among the plurality of caches. In the snoop mechanism, each bus snooper monitors whether a bus command (or a transaction) issued onto the bus influences data stored in its own cache or whether the data stored in its own cache need be returned as a response, and invalidates the data, as needed.
In a copy-back type cache, i.e., a cache which does not immediately reflect data updating by the processor to the main memory, there is case where data (modified data) changed on the cache by the processor to have contents different from those in the main memory must be explicitly written back in the main memory. This operation is required to, e.g., transfer data held by the cache to an input/output device having no snoop mechanism. The operation of writing modified data, which is held by the cache, back in the main memory is called cache flush. A modified cache block is called a modified block.
Cache flush is especially required for a computer using the checkpoint method. In a checkpoint type computer which restarts processing from checkpoint time acquired in advance when some fault occurs in the computer, all modified data which are present only in the cache must be written back (cache flush) in the main memory at each checkpoint time.
To implement the cache flush operation, a system for causing the processor to execute a cache flush instruction or a system for causing a cache flush unit to execute a cache flush instruction is used.
In the method of causing the processor to execute the cache flush instruction, the processor cannot execute another program while it is executing cache flush. Since primary data processing must be stopped, the performance of the entire system degrades. In some processors, all caches are invalidated after executing the cache flush instruction. If all caches are invalidated, all instructions and data must be read out from the main memory again to restart processing, resulting in an increase in overhead in restarting processing. Especially, the system for causing the processor to execute the cache flush instruction cannot employ a two-phase checkpoint scheme (checkpoint acquisition system (Japanese Patent Application No. 7-151739)) which is effective to shorten the cache flush time.
On the other hand, in the system using a cache flush unit, the cache flush unit has a storage section for holding address information associated with a modified block on the cache, and a time is wasted to search for the storage position of the modified block held by the storage section. That is, in checkpoint processing, addresses of all modified blocks must be sequentially read out from the recording means to execute cache flush, and searching for the storage positions of the modified blocks takes a considerable time. This increases overhead especially in checkpoint processing.
Accordingly, it is an object of the present invention to provide a cache flush unit and method which implement fast cache flush and decrease the overhead in checkpoint processing.
According to one aspect of the present invention, there is provided a cache flush unit for use in a computer system having at least one processor with a cache, comprising first storage means for storing address information, associated with modified blocks of caches of all processors, in entries in units of cache lines, and second storage means for storing information to be used to search for an index of one of the entries on the first storage means, one entry containing an address of at least one modified block, wherein the address of the modified block is quickly read out by using the information in the second storage means.
According to another aspect of the present invention, there is provided a cache flush unit for use in a computer system having at least one processor with a cache, comprising first storage means for storing address information, associated with modified blocks of caches of all processors, in entries in units of cache lines, and second storage means for storing, as information to be used to search for an index of one of the entries on the first storage means, one entry containing an address of at least one modified block, data having a value obtained by ORing modified bits of all processors in the entries together with the index, wherein the address of the modified block is quickly read out by using the information in the second storage means.
The cache flush unit may further comprise a first index counter used to search for each index stored in the first storage means in cache flush, and a second index counter used to search for each index stored in the second storage means in cache flush, and the index counters may be selectively used in accordance with a cache flush scheme.
In the cache flush unit, data may be written in the second storage means in units of bits in updating the information.
The cache flush unit may further comprise a write-back buffer group having two hierarchies to sequentially hold write-back requests for the modified blocks, a first hierarchy may have two buffers. One is cache flush processing buffer which is used for cache flush transactions and the other is normal processing buffer which is used for bus transactions issued by processors or other bus agents, and a second hierarchy may have a common buffer.
The cache flush unit may further comprise means for limiting a speed for sending write-back requests for the modified blocks in cache flush.
In the cache flush unit, the data stored in the second storage means may have a plurality of bits holding a plurality of values obtained by ORing the modified bits and also have another bit holding a value obtained by ORing values of the plurality of bits.
In the cache flush unit, only when the OR of the modified bits changes in updating information in the first storage means in normal processing, updating of the information in the second storage means may be requested.
In the cache flush unit, an address map of the information stored in the second storage means may be mapped from a most significant bit side of the index in the first storage means.
In the cache flush unit, index match (index conflict) in the second storage means may be decreased by searching the index in the first storage means using data obtained by replacing upper bits and lower bits of an index output from the first index counter.
The cache flush unit may further comprise means for dynamically switching a cache capacity managed by the first storage means so that the cache capacity is increased to suppress degradation in system performance before switching, and the cache capacity is decreased to shorten a cache flush time after switching.
The cache flush unit may further comprise means for dynamically switching a modified block storage area of the cache managed by the first storage means so that the address information is managed using areas of all processors before switching, and the address information is managed using a storage area of one processor after switching, thereby decreasing an apparent cache capacity.
In the cache flush unit, index match (index conflict) in the second storage means may be decreased by searching the index in the first storage means using data obtained by reversing a bit order of an index output from the first index counter.
The cache flush unit may further comprise means for dynamically switching a cache capacity managed by the first storage means so that the cache capacity is increased to suppress degradation in system performance before switching, and the cache capacity is decreased to shorten a cache flush time after switching while the address information is managed using a storage area of one processor to shorten the cache flush time.
In the cache flush unit, means for updating the address information in accordance with a bus transaction and means for updating the address information by a cache flush operation may be independently arranged to parallelly execute cache information updating according to the bus transaction and cache information updating by the cache flush operation.
The cache flush unit may further comprise speed limiting means for limiting a speed for sending write-back requests for the modified blocks in cache flush, and means for temporarily or continuously invalidating a function of the speed limit means upon detecting that the speed limiting means impedes management of a cache state.
According to still another aspect of the present invention, there is provided a cache flush method for use in a computer system having at least one processor with a cache, comprising the steps of storing address information, associated with modified blocks of caches of all processors, in entries of first storage means in units of cache lines, storing, as information to be used to search for an index of one of the entries on the first storage means, one entry containing an address of at least one modified block, data having a value obtained by ORing modified bits of all processors in the entries of second storage means together with the index, and reading out the address of the modified block quickly by using the information in the second storage means.
The cache flush method may further comprise the step of arranging a first index counter used to search for each index stored in the first storage means in cache flush, and a second index counter used to search for each index stored in the second storage means in cache flush to selectively use the index counters in accordance with a cache flush scheme.
The cache flush method may further comprise the step of arranging a common index counter used to search for each index stored in the first and second storage means in cache flush, and switching connection of the index counter in accordance with a cache flush scheme.
The cache flush method may further comprise the step of, in updating a cache state, writing updated data in units of bits without reading information in the second storage means.
The cache flush method may further comprise the step of independently arranging a unit for updating the address information in accordance with a bus transaction and a unit for updating the address information by a cache flush operation to parallelly execute cache information updating according to the bus transaction and cache information updating by the cache flush operation.
The cache flush method may further comprise the step of independently arranging a unit for updating cache information in accordance with a bus transaction and a unit for updating cache information by a cache flush operation, and independently arranging write-back buffers for sequentially holding write-back requests for the modified blocks on the cache in correspondence with the updating units.
The cache flush method may further comprise the step of independently arranging a unit for updating cache information in accordance with a bus transaction and a unit for updating cache information by a cache flush operation, independently arranging write-back buffers for sequentially holding write-back requests for the modified blocks on the cache at a first stage in correspondence with the updating units, and arranging at a second stage a write-back buffer for commonly receiving outputs from the write-back buffers at the first stage.
The cache flush method may further comprise the step of limiting a speed for sending write-back requests for the modified blocks in cache flush.
The cache flush method may further comprise the step of constituting the data stored in the second storage means by a plurality of bits holding a plurality of values obtained by ORing the modified bits and containing in the data another bit holding a value obtained by ORing values of the plurality of bits.
The cache flush method may further comprise the step of, only when the OR of the modified bits changes in updating information in the first storage means, updating information in the second storage means.
The cache flush method may further comprise the step of mapping address maps in the first and second storage means in opposite orders.
The cache flush method may further comprise the step of searching the index in the first storage means using data obtained by replacing upper bits and lower bits of an index output from the first index counter, thereby decreasing index match (index conflict) in the second storage means.
The cache flush method may further comprise the step of dynamically switching a cache capacity managed by the first storage means so that the cache capacity is increased to suppress degradation in system performance before switching, and the cache capacity is decreased to shorten a cache flush time after switching.
The cache flush method may further comprise the step of dynamically switching a modified block storage area of the cache managed by the first storage means so that the address information is managed using areas of all processors before switching, and the address information is managed using a storage area of one processor after switching, thereby decreasing an apparent cache capacity.
The cache flush method may further comprise the step of searching the index in the first storage means using data obtained by reversing a bit order of an index output from the first index counter, thereby decreasing index match (index conflict) in the second storage means.
The cache flush method may further comprise the step of dynamically switching a cache capacity managed by the first storage means so that the cache capacity is increased to suppress degradation in system performance before switching, and the cache capacity is decreased to shorten a cache flush time after switching while the address information is managed using a storage area of one processor to shorten the cache flush time.
The cache flush method may further comprise the step of limiting a speed for sending write-back requests for the modified blocks in cache flush, and temporarily or continuously invalidating a speed limit upon detecting that the speed limit impedes management of a cache state.
The cache flush method may further comprise the step of partially allowing a write of information of the same index on the second storage means in updating information.
The cache flush method may further comprise the step of managing a cache state on the first storage means in units of processors, and when a transaction for registering a modified line of a first processor at an index corresponding to the modified line of the first processor on the first storage means is generated, and a cache line of a second processor is clean, registering the modified line of the first processor, which has been originally registered, on the cache line of the second processor, and registering a new modified line on a cache line of the first processor, thereby decreasing cache flush caused by bus transactions and minimizing influence on system performance.
The cache flush method may further comprise the step of designating a range of indices on the first storage means, which are to be subjected to cache flush.
The cache flush method may further comprise the step of designating a range of indices on the first storage means, which are to be subjected to cache flush, for each cache flush scheme.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.